#ifndef _TABLE_
#define _TABLE_ 1

#include "Node.h"
#include "pager.h"
#include "results.h"

#define EXIT_SUCCESS 0
#define EXIT_FAILURE 1

// 类似于 Table 的迭代器
class Cursor {
public:
    Cursor(Pager* p, uint32_t pn, uint32_t cn, bool eot): pager(p), page_num(pn), cell_num(cn), end_of_table(eot) {}
    uint32_t getPageNum() { return page_num; }
    uint32_t getUnusedPageNum() { return pager->getNumPages(); }
    uint32_t getCellNum() { return cell_num; }
    void     advance();
    void*    value();
    bool     endOfTable() { return end_of_table; }
private:
    Pager*      pager;
    uint32_t    page_num;
    uint32_t    cell_num;
    bool        end_of_table;
};

// 根据 row_num 计算数据的储存位置
inline void* Cursor::value() {
    void* page = pager->getPage(page_num); // 一个 page 就是一个 node
    return LeafNode::get_value(page, cell_num);
}

void inline Cursor::advance() {
    uint32_t old_page_num = page_num;
    void* node = pager->getPage(page_num);

    cell_num++;
    if (cell_num >= *LeafNode::get_num_cells(node)) {
        end_of_table = true;
    }
}

class Table {
friend class Cursor;
public:
    Table(const char* filename);
    ~Table();
    void                 printBTree(uint32_t page_num, uint32_t indentation_level);
    Cursor               begin();
    Cursor               end();
    bool                 isEmpty();
    bool                 isFull();
    Cursor               find(uint32_t key);
    std::unique_ptr<Row> select(Cursor c);
    ExecuteResult        insert(Row& row_to_insert, Cursor c, uint32_t key);
private:
    Cursor               findLeafNode(uint32_t page_num, uint32_t key);
    void                 splitNodeAndInsert(Cursor& cursor, uint32_t key, Row& value);
    void                 createNewRoot(uint32_t right_child_page_num);
private:
    uint32_t    root_page_num;
    Pager*      pager;
};

/*
    the layout of Table     the layout of a page
    ---------------        ------------------------
    |page (pointer)| --->  |id username email total| (293 Bytes)
    ---------------        ------------------------
    |page (pointer)|       |id username email total| (293 Bytes)
    ---------------        ------------------------
    |...  ...  ... |       |  ...  ... ... ... ... | (total 4096)
*/

inline Table::Table(const char* filename) { 
    pager = new Pager(filename);
    uint32_t fileLength =  pager->getFileLength();
    printf("File length is %d.\n", fileLength);

    root_page_num = 0;

    if (pager->getNumPages() == 0) {
        // New database file. Initialize page 0 as leaf node.
        void* root_node = pager->getPage(0);
        LeafNode::initialize(root_node);
        Node::set_node_root(root_node, true);
    }

    return ;
}

Table::~Table() {
    // save pages before colse
    for (uint32_t i = 0; i <= pager->getNumPages(); i++) {
        if (pager->isNull(i)) continue;
        pager->flush(i);
    }

    // free pager
    delete pager;
}

inline Cursor Table::begin() {
    void* root_node = pager->getPage(root_page_num);
    uint32_t num_cells = *LeafNode::get_num_cells(root_node);
    
    return Cursor (
      pager,
      root_page_num,
      num_cells,
      num_cells == 0  
    );
}

inline Cursor Table::end() {
    void* root_node = pager->getPage(root_page_num);
    uint32_t num_cells = *LeafNode::get_num_cells(root_node);

    return Cursor (
        pager,
        root_page_num,
        num_cells,
        true
    );
}

inline bool Table::isEmpty() {
    void* node = pager->getPage(root_page_num);
    return *LeafNode::get_num_cells(node) == 0;
}

inline bool Table::isFull() {
    void* node = pager->getPage(root_page_num);
    return *LeafNode::get_num_cells(node) >= LEAF_NODE_MAX_CELLS;
}

void Table::printBTree(uint32_t page_num = 0, uint32_t indentation_level = 0) {
    void* node = pager->getPage(page_num);
    uint32_t num_keys, child;
    
    switch (Node::get_node_type(node)) {
    case NodeType::Leaf:
        num_keys = *LeafNode::get_num_cells(node);
        indent(indentation_level);
        printf("- leaf (size %d)\n", num_keys);
        for (uint32_t i = 0; i < num_keys; i++) {
        indent(indentation_level + 1);
        printf("- %d\n", *LeafNode::get_key(node, i));
        }
        break;
    case NodeType::Internal:
        num_keys = *InternalNode::get_num_keys(node);
        indent(indentation_level);
        printf("- internal (size %d)\n", num_keys);
        for (uint32_t i = 0; i < num_keys; i++) {
        child = *InternalNode::get_child(node, i);
        printBTree(child, indentation_level + 1);

        indent(indentation_level + 1);
        printf("- key %d\n", *InternalNode::get_key(node, i));
        }
        child = *InternalNode::get_right_child(node);
        printBTree(child, indentation_level + 1);
        break;
    }
}

Cursor Table::findLeafNode(uint32_t page_num, uint32_t key) {
    void* node = pager->getPage(page_num);
    uint32_t num_cells = *LeafNode::get_num_cells(node);

    // Binary search
    uint32_t min_index = 0;
    uint32_t one_past_max_index = num_cells;
    while (one_past_max_index != min_index) {
        uint32_t index = (min_index + one_past_max_index) / 2; // 不存在溢出的情况
        uint32_t key_at_index = *LeafNode::get_key(node, index);
        if (key == key_at_index) {
            return Cursor(
                pager, 
                page_num, 
                index, 
                index >= *LeafNode::get_num_cells(node)
            );
        } else if (key < key_at_index) {
            one_past_max_index = index;
        } else {
            min_index = index + 1;
        }
    }
    return Cursor (
        pager,
        page_num, 
        min_index,
        min_index >= *LeafNode::get_num_cells(node) 
    );
}

Cursor Table::find(uint32_t key) {
    uint32_t old_root_page_num = root_page_num;
    void* root_node = pager->getPage(root_page_num);

    if (Node::get_node_type(root_node) == NodeType::Leaf) {
        return findLeafNode(root_page_num, key);
    } else {
        printf("Need to implement searching an internal node\n");
        exit(EXIT_FAILURE);
    }
}

void Table::createNewRoot(uint32_t right_child_page_num) {
    /*
    * Old root copied to new page, becomes left child.
    * Address of right child passed in.
    * Re-initialize root page to contain the new root node.
    * New root node points to two children.
    */

    void* root = pager->getPage(root_page_num);
    void* right_child = pager->getPage(right_child_page_num);
    uint32_t left_child_page_num = pager->getNumPages();
    void* left_child = pager->getPage(left_child_page_num);
    // left child has data copied from old root;
    memcpy(left_child, root, PAGE_SIZE);
    Node::set_node_root(left_child, false);
    // Root node is a new internal ndoe with one key and two children
    InternalNode::initialize(root);
    Node::set_node_root(root, true);
    *InternalNode::get_num_keys(root) = 1;
    *InternalNode::get_child(root, 0) = left_child_page_num;
    uint32_t left_child_max_key = Node::get_max_key(left_child);
    *InternalNode::get_key(root, 0) = left_child_max_key;
    *InternalNode::get_right_child(root) = right_child_page_num;
}

void Table::splitNodeAndInsert(Cursor& cursor, uint32_t key, Row& value) {
    /*
    * 当一个节点的cell满之后:
    * 创建新节点, 然后将旧节点中一半的 cell 移到新节点中.
    * 将要插入的值写入到其中一个节点.
    * 更新或者创建父节点.
    */
    
    void* old_node = pager->getPage(cursor.getPageNum());
    // 创建新节点
    uint32_t new_page_num = cursor.getUnusedPageNum();
    void* new_node = pager->getPage(new_page_num);
    LeafNode::initialize(new_node);
    // 复制 cells 
    for (int32_t i = LEAF_NODE_MAX_CELLS; i >= 0; i--) {
        void* destination_node = nullptr;
        if (i >= LEAF_NODE_LEFT_SPLIT_COUNT) {
            destination_node = new_node;
        } else {
            destination_node = old_node;
        }
        uint32_t index_within_node = i % LEAF_NODE_LEFT_SPLIT_COUNT; // 因为 leaf >= right, 所以求余时不会出现重复结果
        void* destination = LeafNode::get_cell(destination_node, index_within_node);

        if (i == cursor.getCellNum()) {
            serialize_row(value, destination);
        } else if (i > cursor.getCellNum()) {
            memcpy(destination, LeafNode::get_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);
        } else {
            memcpy(destination, LeafNode::get_cell(old_node, i), LEAF_NODE_CELL_SIZE);
        }
    }
    // 更新节点中的 num_cells 数据
    *LeafNode::get_num_cells(old_node) = LEAF_NODE_LEFT_SPLIT_COUNT;
    *LeafNode::get_num_cells(new_node) = LEAF_NODE_RIGHT_SPLIT_COUNT;

    if (Node::is_root(old_node)) {
        return createNewRoot(new_page_num);
    } else {
        printf("Need to implement updating parent after split.\n");
        exit(EXIT_FAILURE);
    }
}

ExecuteResult Table::insert(Row& row_to_insert, Cursor c, uint32_t key) {
    printf("get page with page num: %d\n", c.getPageNum());
    void* node = pager->getPage(c.getPageNum());

    printf("num_cells = %d\n", c.getCellNum());

    uint32_t num_cells = *LeafNode::get_num_cells(node);
    if (num_cells >= LEAF_NODE_MAX_CELLS) {
        // Node full
        splitNodeAndInsert(c, key, row_to_insert);
        return ExecuteResult::Success;
    }

    if (c.getCellNum() < num_cells) {
        uint32_t key_at_index = *LeafNode::get_key(node, c.getCellNum());
        if (key_at_index == key) {
            return ExecuteResult::DuplicateKey;
        }
        for (uint32_t i = num_cells; i > c.getCellNum(); i--) {
            memcpy(LeafNode::get_cell(node, i), LeafNode::get_cell(node, i - 1),
                   LEAF_NODE_CELL_SIZE);
        }
    }
    *LeafNode::get_num_cells(node) += 1;
    *LeafNode::get_key(node, c.getCellNum()) = key;
    serialize_row(row_to_insert, LeafNode::get_value(node, c.getCellNum()));

    printf("Run\n");

    return ExecuteResult::Success;
}

inline std::unique_ptr<Row> Table::select(Cursor c) {
    std::unique_ptr<Row> row(new Row);
    deserialize_row(c.value(), row.get());
    return std::move(row);
}

#endif